package algocasts;

public class P12_countPalindromicSubstrings {
    public int P12_countPalindromicSubstrings_DP(String s) {
        if (s == null || s.length() == 0) return 0;
        int n = s.length(), count = 0;
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (i == j) dp[i][j] = true;
                else if (i + 1 == j) dp[i][j] = s.charAt(i) == s.charAt(j);
                else dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
                if (dp[i][j]) count++;
            }
        }
        return count;
    }

    private int expand(String s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
        return count;
    }

    public int P12_countPalindromicSubstrings_Expand(String s) {
        if (s == null || s.length() == 0) return 0;
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            count += expand(s, i, i);
            count += expand(s, i, i + 1);
        }
        return count;
    }

    public static void main(String[] args) {
        P12_countPalindromicSubstrings solution = new P12_countPalindromicSubstrings();
        System.out.println(solution.P12_countPalindromicSubstrings_DP("ababa"));
        System.out.println(solution.P12_countPalindromicSubstrings_Expand("ababa"));
    }
}
